home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Loadstar 12
/
012.d81
/
euclidean articl
< prev
next >
Wrap
Text File
|
2022-08-26
|
1KB
|
89 lines
THE EUCLIDEAN ALGORITHM
The Euclidean Algorithm (or Division
Algorithm) states that given any two
positive integers a and b, there exist
unique non-negative integers a and b
such that
a = bq + r WITH 0 <= r < b.
Note: The combination of symbols <=
is the BASIC notation for 'less than
or equal to'. We adopt it for these
articles since the usual symbols are
not available.
Query: Is there a suitable extension
of the Algorithm which includes the
negative integers as well? Extension
in this context means that the
extended algorithm must agree with
the algorithm above if a and b are
both positive. By the way, the answer
is yes. See if you can come up with a
statement. Try
A=BG+R 0<=R<=ABS(B)
or
A=BG+R 0<=ABS(R)<ABS(B)
where ABS(X) denotes the absolute of
X.
Example: Let a=25 and b=6. Then since
6 'goes into' 25 four times with a
remainder of one', q=4 and r=1 are the
integers guaranteed by the Algorithm.
The uniqueness of q and r is also
guaranteed by the Algorithm. Try to
find another pair of integers, q' and
r' such that
25 = 6q' + r' 0 <= r' < 6.
For example, what's wrong with q'=3
and r'=7?
As a final comment on the Euclidean
Algorithm, you may not be used to the
way we have stated it, and you may not
recognize it in this form, but if you
can do long division, you already know
the Euclidean Algorithm.
--------------------------------------